#ifndef __WIZ_DATATYPE_BINARYTREE_HPP__SHANHAOBO_19800429__
#define __WIZ_DATATYPE_BINARYTREE_HPP__SHANHAOBO_19800429__

#include "../../Base/WizBase.hpp"

namespace Wiz
{
    namespace BinaryTree
    {
        enum eInsertType
        {
            eInsertHere,
            eInsertLeft,
            eInsertRight,
        };
        template<class ElementT>
        class Type
        {
            WIZ_DECLARE_CLASS_THIS(Type);
        protected:
            //////////////////////////////////////////////////////////////////////////
            tThisPtr			m_Left;
            tThisPtr			m_Right;
            ElementT		    m_Data;
            //////////////////////////////////////////////////////////////////////////
        public:
            Type() : m_Left(WIZ_NULLPTR), m_Right(WIZ_NULLPTR)
            {
            }
            Type(const ElementT& Dt) : m_Left(WIZ_NULLPTR), m_Right(WIZ_NULLPTR), m_Data(Dt)
            {
            }
            ~Type()
            {
            }
        public:
            ::Wiz::Void::Type Set(const ElementT& D)
            {
                m_Data = D;
            }
            ElementT& Get()
            {
                return m_Data;
            }
            const ElementT& Get() const
            {
                return m_Data;
            }
        public:
            ::Wiz::Bool::Type SetLeft(tThisPtr Node)
            {
                WIZ_ASSERT(::Wiz::IsValidPtr(Node));
                if (::Wiz::IsValidPtr(m_Left))
                {
                    return ::Wiz::Bool::False;
                }

                m_Left = Node;
                return ::Wiz::Bool::True;
            }
            ::Wiz::Bool::Type SetRight(tThisPtr Node)
            {
                WIZ_ASSERT(::Wiz::IsValidPtr(Node));
                if (::Wiz::IsValidPtr(m_Right))
                {
                    return ::Wiz::Bool::False;
                }

                m_Right = Node;
                return ::Wiz::Bool::True;
            }
        public:
            tThisPtr InsertLeft()
            {
                if (::Wiz::IsValidPtr(m_Left))
                {
                    return WIZ_NULLPTR;
                }
                tThisPtr newPtr = new tThis();
                if (::Wiz::IsValidPtr(newPtr))
                {
                    m_Left = newPtr;
                    return m_Left;
                }

                return WIZ_NULLPTR;
            }
            tThisPtr InsertRight()
            {
                if (::Wiz::IsValidPtr(m_Right))
                {
                    return WIZ_NULLPTR;
                }
                tThisPtr newPtr = new tThis();
                if (::Wiz::IsValidPtr(newPtr))
                {
                    m_Right = newPtr;
                    return m_Right;
                }

                return WIZ_NULLPTR;
            }
        public:
            tThisPtr RemoveLeft()
            {
                tThisPtr Left = m_Left;
                m_Left = WIZ_NULLPTR;
                return Left;
            }
            tThisPtr RemoveRight()
            {
                tThisPtr Right = m_Right;
                m_Right = WIZ_NULLPTR;
                return Right;
            }
        public:
            tThisPtr GetLeft()
            {
                return m_Left;
            }
            tThisPtr GetRight()
            {
                return m_Right;
            }
        public:
            template<class InsertFunc>
            ::Wiz::Bool::Type Insert(tThisPtr Node)
            {
                return InsertHelper<InsertFunc>(NULL, this, Node);
            }
        protected:
            template<class InsertFunc>
            ::Wiz::Bool::Type InsertHelper(tThisPtr Parent, tThisPtr Curr, tThisPtr Node)
            {
                WIZ_ASSERT(::Wiz::IsValidPtr(Curr));
                WIZ_ASSERT(::Wiz::IsValidPtr(Node));
                const eInsertType eIT = InsertFunc(Parent, Curr, Node);
                if (eIT == eInsertHere)
                {
                    if (::Wiz::IsValidPtr(Parent))
                    {
                        if (Parent->m_Left == Curr)
                        {
                            Parent->m_Left = Node;
                        }
                        else
                        {
                            WIZ_ASSERT(Parent->m_Right == Curr);
                            Parent->m_Right = Node;
                        }
                    }
                    /// Check Dead Loop
                    WIZ_ASSERT(InsertFunc(Parent, Node, Curr) != eInsertHere);
                    return InsertHelper<InsertFunc>(Parent, Node, Curr);
                }
                else if (eIT == eInsertLeft)
                {
                    if (::Wiz::IsNull(Curr->m_Left))
                    {
                        Curr->m_Left = Node;
                        return ::Wiz::Bool::True;
                    }
                    return InsertHelper<InsertFunc>(Curr, Curr->m_Left, Node);
                }
                WIZ_ASSERT(eIT == eInsertRight);
                if (::Wiz::IsNull(Curr->m_Right))
                {
                    Curr->m_Right = Node;
                    return ::Wiz::Bool::True;
                }
                return InsertHelper<InsertFunc>(Curr, Curr->m_Right, Node);
            }
        public:
            template<class InsertFunc>
            ::Wiz::Bool::Type Insert(const ElementT& D)
            {
                return InsertHelper<InsertFunc>(this, D);
            }
        protected:
            template<class InsertFunc>
            ::Wiz::Bool::Type InsertHelper(tThisPtr Curr, const ElementT& D)
            {
                WIZ_ASSERT(::Wiz::IsValidPtr(Curr));
                WIZ_ASSERT(::Wiz::IsValidPtr(Node));
                const eInsertType eIT = InsertFunc(Curr, D);
                if (eIT == eInsertHere)
                {
                    Curr->Set(D);
                }
                else if (eIT == eInsertLeft)
                {
                    if (::Wiz::NotValidPtr(Curr->m_Left))
                    {
                        tThis* newPtr = new tThis(D);
                        if (::Wiz::IsValidPtr(newPtr))
                        {
                            Curr->m_Left = newPtr;
                            return ::Wiz::Bool::True;
                        }
                        return ::Wiz::Bool::False;
                    }
                    return InsertHelper<InsertFunc>(Curr, Curr->m_Right, D);
                }
                WIZ_ASSERT(eIT == eInsertRight);
                if (::Wiz::NotValidPtr(Curr->m_Right))
                {
                    tThis* newPtr = new tThis(D);
                    if (::Wiz::IsValidPtr(newPtr))
                    {
                        Curr->m_Right = newPtr;
                        return ::Wiz::Bool::True;
                    }
                    return ::Wiz::Bool::False;
                }
                return InsertHelper<InsertFunc>(Curr, Curr->m_Right, D);
            }
        public:
            template<class TraversalFunc>
            ::Wiz::Void::Type PreOrderTraversal()
            {
                PreOrderTraversalHelper<TraversalFunc>(this);
            }
        protected:
            template<class TraversalFunc>
            ::Wiz::Void::Type PreOrderTraversalHelper(tThisPtr Node)
            {
                WIZ_ASSERT(::Wiz::IsValidPtr(Node));
                TraversalFunc(m_Data);
                if (::Wiz::IsValidPtr(Node->m_Left))
                {
                    PreOrderTraversalHelper(Node->m_Left);
                }
                if (::Wiz::IsValidPtr(Node->m_Right))
                {
                    PreOrderTraversalHelper(Node->m_Right);
                }
            }
        public:
            template<class TraversalFunc>
            ::Wiz::Void::Type InOrderTraversal()
            {
                InOrderTraversalHelper<TraversalFunc>(this);
            }
        protected:
            template<class TraversalFunc>
            ::Wiz::Void::Type InOrderTraversalHelper(tThisPtr Node)
            {
                WIZ_ASSERT(::Wiz::IsValidPtr(Node));
                if (::Wiz::IsValidPtr(Node->m_Left))
                {
                    InOrderTraversalHelper(Node->m_Left);
                }
                TraversalFunc(m_Data);
                if (::Wiz::IsValidPtr(Node->m_Right))
                {
                    InOrderTraversalHelper(Node->m_Right);
                }
            }
        public:
            template<class TraversalFunc>
            ::Wiz::Void::Type PostOrderTraversal()
            {
                PostOrderTraversalHelper<TraversalFunc>(this);
            }
        protected:
            template<class TraversalFunc>
            ::Wiz::Void::Type PostOrderTraversalHelper(tThisPtr Node)
            {
                WIZ_ASSERT(::Wiz::IsValidPtr(Node));
                if (::Wiz::IsValidPtr(Node->m_Left))
                {
                    PostOrderTraversalHelper(Node->m_Left);
                }
                TraversalFunc(m_Data);
                if (::Wiz::IsValidPtr(Node->m_Right))
                {
                    PostOrderTraversalHelper(Node->m_Right);
                }
            }
        }; /// end of struct Type
    } /// end of namespace BinaryTree
} /// end of namespace Wiz

#endif /*__WIZ_DATATYPE_TREE_HPP__SHANHAOBO_19800429__*/
